\documentclass[11pt,a4paper,twoside]{scrartcl}
\usepackage{palatino}
\usepackage {graphicx}
\usepackage{setspace}
\usepackage{ngerman}
%\usepackage[ngerman]{babel}
\usepackage{cite}
\usepackage{a4wide}
\usepackage{float}
\usepackage{amsmath,amsfonts,array,theorem}
\usepackage{graphicx}
\usepackage{version}
\usepackage{listings}
\lstloadlanguages{java}
\usepackage{paraprogramming}
\usepackage{color}
\usepackage{algorithmic}
\usepackage{verbatim} 
\usepackage{boxedminipage}
%\setlength{\tabcolsep}{10pt}
\renewcommand{\arraystretch}{1.5}
\usepackage[latin1]{inputenc}
\usepackage{tikz}
\usepackage{xfrac}
\usepackage{longtable}
\usepackage{framed}
\usetikzlibrary{automata}
\usetikzlibrary{fit}
\usetikzlibrary{backgrounds}
\usetikzlibrary{arrows}
\usetikzlibrary{shapes}
\usetikzlibrary{positioning}
\usetikzlibrary{shadows}
\pagestyle{empty}
\usepackage{lscape}

\usepackage{fancyhdr}
\interfootnotelinepenalty=10000
\widowpenalty=3000
\clubpenalty=3000

%%%%%%%%%%%%%%%%%%%

\newcommand{\U}[1]{
    \textcolor{red}{\bfseries\sffamily(#1)}
    \marginpar{\textcolor{red}{\bfseries\sffamily U}}
  }
\newcommand{\K}[1]{
    \textcolor{blue}{\bfseries\sffamily(#1)}
    \marginpar{\textcolor{blue}{\bfseries\sffamily K}}
  }
\newcommand{\T}[1]{
    \textcolor{green}{\bfseries\sffamily(#1)}
    \marginpar{\textcolor{green}{\bfseries\sffamily T}}
  }

%%%%%%%%%%%%%%%%%%%


\begin{document}
\parindent0pt
\thispagestyle{fancy}
\pagestyle{fancy}
\rhead[]{\rightmark}
\lhead[\leftmark]{}


\onehalfspacing

\begin{center}
	{\bf \Large{\textbf{Parallel Programming Assignment 1}}} \\
	Mai 5, 2011
	\vspace{7mm}

	\begin{tabular}{|c|c|}
	\hline
	Name & Matriculation Number \\
	\hline
	Xiaofeng Xu & 329487\\
	\hline
	 Tsvetelina Yonova & 312208 \\
	\hline
	\end{tabular}
\end{center}

\begin{enumerate}
	\item Exercise done.
	\item Exercise See Implementation
	\item Exercise
	
			\begin{enumerate}
				\item With every send operation we have a latency of $\alpha + \frac{n}{\beta}$ where $\frac{n}{\beta}$ is the time needed to transfer $n$ bytes with bandwith of $\beta$ bytes per second and $\alpha$ is the given node to node latency. Since every process sends the message to the next, we have $p-1$ send opertations and since they are done sequentially we compute the time needed to complete the operation with the formula:
				
				$$(\alpha + \frac{n}{\beta})(p-1)$$
				\item 
				\item We propose two different ways to speed up the process:
				
				
					\begin{itemize}
						\item First we can try to increase the parallelism of the system. So given a network of $p$ nodes we can do following: node $1$ sends the message to node $p$. Then nodes $1$ and $p$ send simultaneously the message to nodes $2$ and $p-1$. In the next step nodes $2$ and $p-1$ send the message to nodes $3$ and $p-2$ and so on until they reach the middle: 			

							
								\begin{tabular}{|l|l|}\hline
									First step & $1  \stackrel{send}{\longrightarrow} p$\\
									\hline
									Second step & $1  \stackrel{send}{\longrightarrow} 2$\\
									& $p \stackrel{send}{\longrightarrow} p-1$\\
									\hline
									Third step & $2 \stackrel{send}{\longrightarrow} 3$\\
									& $p-1 \stackrel{send}{\longrightarrow} p-2$ \\
									\hline
									And so on & \\
									\hline
								\end{tabular}
						
						Since we know the exact number of nodes we can compute the middle and determine when to stop transmitting. Also we can define only one node to send the message to the middle node if we have an uneven number of nodes. In this way we gain a twice faster broadcast process since we send two messages at a time. So the formula is:
						
						$$(\alpha + \frac{n}{\beta})\frac{p}{2}$$
						\item Using the idea of the previous method, we can speed up the broadcast even more if we define an algorithm that uses all nodes that have the message as senders:
						
							\begin{tabular}{|l|l|}\hline
									First step & $1  \stackrel{send}{\longrightarrow} 2$\\
									\hline
									Second step & $1  \stackrel{send}{\longrightarrow} 3$\\
									& $2 \stackrel{send}{\longrightarrow} 4$\\
									\hline
									Third step & $1 \stackrel{send}{\longrightarrow} 5$\\
									& $2 \stackrel{send}{\longrightarrow} 6$ \\
									& $3 \stackrel{send}{\longrightarrow} 7$\\
									& $4 \stackrel{send}{\longrightarrow} 8$\\
									\hline
									And so on & \\
									\hline
								\end{tabular}
								
								So in this case we also have $\alpha + \frac{n}{\beta}$ latency pro step, but we have less steps. The number of sending nodes is growing exponentially with every step. Thus the number of steps is growing only logarithmically with every new node. Therefore we have the formula: 
						$$(\alpha + \frac{n}{\beta})\log_2p$$
					\end{itemize}
				\item See Implementation
			\end{enumerate}
\end{enumerate}
\end{document}
  
	